package MyBinaryTree;

public class HuffmanTree {
    // 构造哈夫曼树

    public HuffmanTree(int [] w){
        // w 传入的字符
        int l = w.length;
        // 哈夫曼树的结点数
        int n = 2*l - 1;

        HuffmanNode[] node = new HuffmanNode[n];
        // 构造权重为 w[i] 的结点
        for(int i=0; i<l; i++){
            node[i] = new HuffmanNode(w[i]);
        }

        // 构造哈夫曼树
        for(int i=n; i>0; i--){
            HuffmanNode m1 = selectMin(node, i-1);
            // 这里设置flag后在下面寻找第二小的时就可以避免查找同一个结点
            m1.flag = 1;
            HuffmanNode m2 = selectMin(node, i-1);
            m2.flag = 1;
            // 构造做左孩子
            node[i].lchild = m1;
            // 构造右孩子
            node[i].rchild = m2;
            // 构造一个新的二叉树
            node[i].weight = m1.weight + m2.weight;

            m1.parent = node[i];
            m2.parent = node[i];
        }
    }


    public HuffmanNode selectMin(HuffmanNode[] node, int i){
        // 寻找不在树中的权重最小的点
        HuffmanNode min = node[i];
        for(int j=0; j<=i; j++){
            if(node[j].weight < min.weight && node[j].flag==0){
                min = node[j];
            }
        }
        return min;
    }


    public int[][] HuffmanCode(HuffmanNode[] node, int n){
        int[][] HuffmanCode = new int[n][n];
        for(int i=0; i<n; i++){
            int k = n-1;
            HuffmanNode t = node[i];
            HuffmanNode p = t.parent;
            for(; p!=null; p=p.parent){
                if(p.lchild==t){
                    HuffmanCode[i][k--]=0;
                }else{
                    HuffmanCode[i][k--]=1;
                }
            }
        }
        return HuffmanCode;
    }


}
